package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //全排列II
        class Solution {
            private List<List<Integer>> res;
            private List<Integer> path;
            private boolean[] used;

            public List<List<Integer>> permuteUnique(int[] nums) {
                Arrays.sort(nums);                 // 1) 排序，使相同元素相邻
                int n = nums.length;
                res = new ArrayList<>();
                path = new ArrayList<>();
                used = new boolean[n];
                dfs(nums, 0);
                return res;
            }

            private void dfs(int[] nums, int depth) {
                if (depth == nums.length) {        // 2) 叶子：收集答案
                    res.add(new ArrayList<>(path));
                    return;
                }
                for (int i = 0; i < nums.length; i++) {
                    if (used[i]) continue;         // 已用过，跳过

                    // 3) 同层去重：相同元素只允许第一个进入本层分支
                    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

                    // 4) 选择
                    used[i] = true;
                    path.add(nums[i]);

                    // 5) 递归下一层
                    dfs(nums, depth + 1);

                    // 6) 回溯
                    path.remove(path.size() - 1);
                    used[i] = false;
                }
            }
        }

        //话号码的字母组合
        class Solution2 {
            // 电话键映射
            private static final String[] KEYS = {
                    "",     // 0
                    "",     // 1
                    "abc",  // 2
                    "def",  // 3
                    "ghi",  // 4
                    "jkl",  // 5
                    "mno",  // 6
                    "pqrs", // 7
                    "tuv",  // 8
                    "wxyz"  // 9
            };

            private List<String> res = new ArrayList<>();
            private StringBuilder path = new StringBuilder();

            public List<String> letterCombinations(String digits) {
                if (digits == null || digits.length() == 0) return res; // 空输入
                dfs(digits, 0);
                return res;
            }

            private void dfs(String digits, int pos) {
                if (pos == digits.length()) {          // 叶子：收集结果
                    res.add(path.toString());
                    return;
                }
                int idx = digits.charAt(pos) - '0';    // 当前位对应的按键
                String letters = KEYS[idx];

                for (int i = 0; i < letters.length(); i++) {
                    path.append(letters.charAt(i));    // 选择一个字母
                    dfs(digits, pos + 1);              // 递归下一位
                    path.deleteCharAt(path.length() - 1); // 回溯撤销
                }
            }
        }
    }
}